机器学习


基本概念

计算机学院    张腾

tengzhang@hust.edu.cn

大纲

人工智能逻辑推理知识工程机器学习任务类型模型方法监督学习半监督学习无监督学习分类回归排序聚类降维密度估计符号学派连接学派统计学派类推学派决策树感知机神经网络朴素贝叶斯k-近邻支持向量机

机器学习

一般流程

g cluster_1 特征工程 原始数据 原始数据  特征提取    特征提取   原始数据 ->  特征提取    特征处理    特征处理    特征提取  ->  特征处理   特征变换 特征变换  特征处理  ->特征变换 模型学习 模型学习 特征变换->模型学习 预测 预测 模型学习->预测

原始数据:表格、图片、视频、文本、语音、……

特征工程:

  • 提取:选取、构造对目标任务有用的潜在特征
  • 处理:无序的离散类别特征 → 数值特征,缺失处理,标准化
  • 变换:对特征进行挑选或映射得到对目标任务更有效的特征

模型学习:最核心的部分,学习一个用来预测的映射

监督学习

所有样本都有类别标记

原始数据 样本/示例 属性/特征 标记
$o_1$ $(\xv_1, y_1)$ $\xv_1[1:d]$ $y_1$
$o_2$ $(\xv_2, y_2)$ $\xv_2[1:d]$ $y_2$
$\vdots$ $\vdots$ $\vdots$ $\vdots$
$o_m$ $(\xv_m, y_m)$ $\xv_m[1:d]$ $y_m$

任务类型:

  • 二分类:$y \in \{ 1, -1 \}$或者$y \in \{ 0,1 \}$
  • 多分类:$y \in [C] = \{ 1, 2, \ldots, C \}$
  • 回归:$y \in \Rbb$或连续集合
  • 结构预测:$y$可以是向量、序列、语法树、……
二分类示例

多分类示例

混淆矩阵

回归

线性回归:用最小二乘求解超定方程组 (方程个数比未知数多)

半监督学习

只有部分样本有类别标记,如何利用其它未标记样本?

原始数据 样本/示例 属性/特征 标记
$o_1$ $(\xv_1, y_1)$ $\xv_1[1:d]$ $y_1$
$\vdots$ $\vdots$ $\vdots$ $\vdots$
$o_l$ $(\xv_l, y_l)$ $\xv_m[1:d]$ $y_l$
$o_{l+1}$ $(\xv_{l+1}, -)$ $\xv_{l+1}[1:d]$ $-$
$\vdots$ $\vdots$ $\vdots$ $\vdots$
$o_{l+u}$ $(\xv_{l+u}, -)$ $\xv_{l+u}[1:d]$ $-$

任务类型:

  • 转导 (transductive) 学习:预测$\xv_{l+1}, \ldots, \xv_{l+u}$的类别标记
  • 归纳 (inductive) 学习:必须有显式模型,能对未知样本进行预测
无监督学习

所有样本都没有类别标记

原始数据 样本/示例 属性/特征 标记
$o_1$ $(\xv_1, -)$ $\xv_1[1:d]$ $-$
$o_2$ $(\xv_2, -)$ $\xv_2[1:d]$ $-$
$\vdots$ $\vdots$ $\vdots$ $\vdots$
$o_m$ $(\xv_m, -)$ $\xv_m[1:d]$ $-$

任务类型:

  • 聚类 (clustering):依相似度将数据分成$K$个簇 (cluster)
  • 降维/嵌入:为样本学习新的特征
  • 密度估计:估计样本空间的概率密度$\Pr(\xv)$,寻找数据的生成机制
聚类

  • 原始数据由 6 个簇组成
  • K 均值算法指定聚成 4 个簇,每种颜色对应一个簇,菱形为簇中心
密度估计

  • 直方图是最简单的密度估计方法 (数数),对区间的选择极其敏感
  • 核密度估计:$\rho(\zv) = \sum_{i \in [m]} \kappa ((\zv-\xv_i)/\sigma)$
密度估计

  • 核密度估计:$\rho(\zv) = \sum_{i \in [m]} \kappa ((\zv-\xv_i)/\sigma)$
大纲

人工智能逻辑推理知识工程机器学习任务类型模型方法监督学习半监督学习无监督学习分类回归排序聚类降维密度估计符号学派连接学派统计学派类推学派决策树感知机神经网络朴素贝叶斯k-近邻支持向量机

机器学习方法分类

米哈尔斯基 等《机器学习:一种人工智能途径》
Machine Learning: An Artificial Intelligence Approach

  • 从样本中学习
  • 在问题求解和规划中学习
  • 通过观察和发现学习
  • 从指令中学习

费根鲍姆 等《人工智能手册》
The Handbook of Artificial Intelligence

  • 机械学习,死记硬背式学习,信息存储检索
  • 示教学习,类似于“从指令中学习”
  • 类比学习,类似于“通过观察和发现学习”
  • 归纳学习,类似于“从样本中学习”,目前研究最多、应用最广
机器学习流派

多明戈斯 Pedro Domingos
《终极算法》The Master Algorithm

  • 符号学派:规则学习,决策树
  • 连接学派:感知机,神经网络
  • 进化学派
  • 统计学派:朴素贝叶斯,贝叶斯网
  • 类推学派:k-近邻,支持向量机

灵魂问题:哪个算法更好?

没有免费的午餐定理 (No Free Lunch Theorem, NFL 定理)

  • 脱离具体的问题空谈什么算法好没有意义
  • 学习算法自身的归纳偏好应与问题相匹配
约还是不约?

约会次序 约会时间 约会方式 当天温度 当天电视 答应约会
1 周末 吃饭 暖和 不好看
2 周末 逛街 暖和 好看
3 周末 逛街 暖和 不好看
4 周末 逛街 炎热 好看
5 周末 逛街 炎热 不好看 ?

女人心海底针 让机器学习读心术来拯救你

符号学派

约会次序 约会时间 约会方式 当天温度 当天电视 答应约会
1 周末 吃饭 暖和 不好看
2 周末 逛街 暖和 好看
3 周末 逛街 暖和 不好看
4 周末 逛街 炎热 好看
5 周末 逛街 炎热 不好看 ?

用“若……且……且……则……”形式的合取规则覆盖数据

$(\text{方式} = \text{逛街}) \wedge (\text{温度} = \text{暖和}) \rightarrow \text{约会}$

  • 可解释强,用户可以秒懂
  • 学习中易于引入人类知识
连接学派

约会次序 约会时间 约会方式 当天温度 当天电视 答应约会
1 周末 吃饭 暖和 不好看
2 周末 逛街 暖和 好看
3 周末 逛街 暖和 不好看
4 周末 逛街 炎热 好看
5 周末 逛街 炎热 不好看 ?

带阈值的线性函数拟合数据

$\sgn(w_0 + w_1 \times \text{次序} + \cdots + w_5 \times \text{电视}) \rightarrow \{\text{是}, \text{否}\}$

  • 知识是分布式存储的,由权重系数$w_0, w_1, \ldots, w_5$表示
  • 将上述函数广泛并行串联就是神经网络
统计学派

约会次序 约会时间 约会方式 当天温度 当天电视 答应约会
1 周末 吃饭 暖和 不好看
2 周末 逛街 暖和 好看
3 周末 逛街 暖和 不好看
4 周末 逛街 炎热 好看
5 周末 逛街 炎热 不好看 ?

利用贝叶斯公式求后验概率

$\Pr (\text{约会}|\text{次序},\ldots,\text{电视}) = \frac{\Pr (\text{次序},\ldots,\text{电视}|\text{约会}) \Pr (\text{约会}) \qquad \quad}{\Pr (\text{次序},\ldots,\text{电视}) \qquad}$

  • 先验$\Pr (\text{约会})$反映了在没有任何信息的情况下成功约会的信念
  • 数据通过似然$\Pr (\text{次序},\ldots,\text{电视}|\text{约会})$调整我们对成功约会的信念
类推学派

约会次序 约会时间 约会方式 当天温度 当天电视 答应约会
1 周末 吃饭 暖和 不好看
2 周末 逛街 暖和 好看
3 周末 逛街 暖和 不好看
4 周末 逛街 炎热 好看
5 周末 逛街 炎热 不好看 ?

借鉴相似的样本,据此做预测

  • 过往越相似的样本,参考价值越大
  • 对待预测的样本 5,其与样本 3、样本 4 均只有一个属性不同
  • 根据样本 3、样本 4 的经验进行预测,答应约会的概率为 50%
模型评估 回归

给定模型$f$、数据集$D = \{ (\xv_i, y_i) \}_{i \in [m]}$

均方误差 (mean squared error, MSE)

$$ \begin{align*} E(f;D) = \frac{1}{m} \sum_{i \in [m]} (f(\xv_i) - y_i)^2 \end{align*} $$

>>> from sklearn.metrics import mean_squared_error

>>> y_true = [3, -0.5, 2, 7]
>>> y_pred = [2.5, 0.0, 2, 8]

>>> mean_squared_error(y_true, y_pred) # MSE
0.375

>>> mean_squared_error(y_true, y_pred, squared=False) # RMSE
0.6123724356957945
模型评估 分类

给定模型$f$、数据集$D = \{ (\xv_i, y_i) \}_{i \in [m]}$

错误率 (error rate)、精度 (accuracy)

$$ \begin{align*} E(f;D) = \frac{1}{m} \sum_{i \in [m]} \Ibb (f(\xv_i) \ne y_i), ~ \acc(f;D) = 1 - E(f;D) \end{align*} $$

>>> from sklearn.metrics import accuracy_score

>>> y_true = [0, 1, 2, 3]
>>> y_pred = [0, 2, 1, 3]

>>> accuracy_score(y_true, y_pred) # 百分比
0.5

>>> accuracy_score(y_true, y_pred, normalize=False) # 正确分类的个数
2
查准率 查全率 F1

二分类结果的混淆矩阵 (confusion matrix)

预测 正例 实际 负例
真实 正例 $\TP$ (真正例) $\FN$ (假反例)
真实 负例 $\FP$ (假正例) $\TN$ (真反例)

查准率 (precision):预测的约会中有多少比例真的约会了

查全率 (recall):所有的约会中有多少比例被预测出来了

$$ \begin{align*} & \mathrm{precision} = \frac{\TP}{\TP + \FP}, \quad \mathrm{recall} = \frac{\TP}{\TP + \FN} \\[4pt] & \mathrm{F1} = \frac{2 \times \mathrm{Precision} \times \mathrm{Recall}}{\mathrm{Precision} + \mathrm{Recall}} = \frac{2 \times \TP}{\text{样本总数} + \TP - \TN \quad} \end{align*} $$

查准率 查全率 F1

>>> from sklearn.metrics import confusion_matrix
>>> from sklearn.metrics import precision_score, recall_score, f1_score

>>> y_true = [1, 1, 0, 0, 1, 0, 1, 0]
>>> y_pred = [0, 1, 0, 1, 1, 1, 1, 0]

>>> cm = confusion_matrix(y_true, y_pred, labels=[1,0])
>>> cm
array([[3, 1],
       [2, 2]])

>>> tp, fn, fp, tn = cm.ravel()
>>> tp, fn, fp, tn
(3, 1, 2, 2)

>>> precision_score(y_true, y_pred)
0.6

>>> recall_score(y_true, y_pred)
0.75

>>> f1_score(y_true, y_pred)
0.6666666666666665
模型选择 回归

选择宗旨:在未知数据上表现好,即泛化 (generalization) 好

给定模型$f$、训练数据集$D = \{ (\xv_i, y_i) \}_{i \in [m]}$,其中$\xv_i \sim \Dcal$

训练 (training) 均方误差、经验 (empirical) 均方误差

$$ \begin{align*} E(f;D) = \frac{1}{m} \sum_{i \in [m]} (f(\xv_i) - y_i)^2 \end{align*} $$

泛化均方误差

$$ \begin{align*} E(f;\Dcal) = \Ebb_{\xv \sim \Dcal} [(f(\xv) - y)^2] = \Ebb_{D \sim \Dcal^m} [E(f;D)] \end{align*} $$

模型选择 分类

选择宗旨:在未知数据上表现好,即泛化 (generalization) 好

给定模型$f$、训练数据集$D = \{ (\xv_i, y_i) \}_{i \in [m]}$,其中$\xv_i \sim \Dcal$

训练 (training) 错误率、经验 (empirical) 错误率

$$ \begin{align*} E(f;D) = \frac{1}{m} \sum_{i \in [m]} \Ibb (f(\xv_i) \ne y_i) \end{align*} $$

泛化错误率

$$ \begin{align*} E(f;\Dcal) = \Ebb_{\xv \sim \Dcal} [\Ibb(f(\xv) \ne y)] = \Ebb_{D \sim \Dcal^m} [E(f;D)] \end{align*} $$

欠拟合 过拟合

训练集:余弦函数中随机采样的$30$个点加上$0.1$的随机噪声

学习算法:$n$多项式回归$n=1$即为线性回归

$$ \begin{align*} \min_{w_j} ~ g (w_j) = \frac{1}{2} \sum_{i \in [30]} \left( \sum_{j=0}^n w_j x_i^j - y_i \right)^2 \end{align*} $$

其中$w_0, w_1, \ldots, w_n$为待求参数

目标函数$g$关于$w_j$的偏导数为

$$ \begin{align*} \frac{\partial g}{\partial w_j} = \sum_{i \in [30]} \left( \sum_{j=0}^n w_j x_i^j - y_i \right) x_i^j \end{align*} $$

欠拟合 过拟合

左图:1 阶多项式欠拟合 (underfitting)

中图:4 阶多项式拟合地最好

右图:15 阶多项式过拟合 (overfitting)

模型选择 验证

事先选定合适的模型 (归纳偏倚) 很重要!

从训练集中随机选择一部分样本作为验证集 (validation set)

  • 在剩余的训练集上训练一个学习模型
  • 在验证集上计算模型的误差

据此比较多个候选模型的性能

交叉验证 (cross validation):将训练集平均分为$n$份,每轮

  • 在其中$n-1$份上训练一个学习模型
  • 在剩余的$1$份上计算模型的误差

迭代$n$轮取平均,据此比较多个候选模型的性能

偏差方差分解

对任意样本$\xv$,设

  • $y$为其真实标记
  • $y_D$为其在数据集$D$中的标记,可能不等于$y$,即存在噪声
  • $f(\xv;D)$为数据集$D$上的训得的模型$f$$\xv$的预测

对回归任务,样本数相同的不同数据集$D \sim \Dcal^m$,学习算法的

  • 噪声为$\varepsilon^2 = \Ebb_D [(y_D - y)^2]$,并假定噪声期望为零,即$\Ebb_D [y_D - y] = 0$
  • 期望预测为$\bar{f}(\xv) = \Ebb_D [f(\xv; D)]$
  • 预测方差为$\var(\xv) = \Ebb_D [(f(\xv; D) - \bar{f}(\xv))^2]$数据扰动造成的影响
  • 预测偏差为$\bias^2(\xv) = (\bar{f}(\xv) - y)^2$学习算法本身的拟合能力

下面考虑对期望泛化误差$\Ebb_D [(f(\xv; D) - y_D)^2]$进行分解

偏差方差分解

$$ \begin{align*} & \qquad \Ebb_D [(f(\xv; D) - y_D)^2] \\ & = \Ebb_D [(f(\xv; D) \class{yellow}{- \bar{f}(\xv) + \bar{f}(\xv)} - y_D)^2] \\ & = \underbrace{\Ebb_D [(f(\xv; D) - \bar{f}(\xv))^2]}_{\var(\xv)} + \Ebb_D [(\bar{f}(\xv) - y_D)^2] \\ & \qquad \qquad + 2 \Ebb_D [(f(\xv; D) - \bar{f}(\xv))(\bar{f}(\xv) - y_D)] \\ & = \var(\xv) + \Ebb_D [(\bar{f}(\xv) - y_D)^2] + 2 (\bar{f}(\xv) - y_D) \underbrace{\Ebb_D [(f(\xv; D) - \bar{f}(\xv))]}_{0} \\ & = \var(\xv) + \Ebb_D [(\bar{f}(\xv) \class{yellow}{- y + y} - y_D)^2] \\ & = \var(\xv) + \Ebb_D [(\bar{f}(\xv) - y)^2] + \underbrace{\Ebb_D [(y - y_D)^2]}_{\varepsilon^2} + 2 \Ebb_D [(\bar{f}(\xv) - y)(y - y_D)] \\ & = \var(\xv) + \underbrace{(\bar{f}(\xv) - y)^2}_{\bias^2(\xv)} + \varepsilon^2 + 2 (\bar{f}(\xv) - y) \underbrace{\Ebb_D [y - y_D]}_{0} \\ & = \var(\xv) + \bias^2(\xv) + \varepsilon^2 \end{align*} $$

偏差方差分解